package com.bravo.other.knapsack;

public class dichotomy {

    public static void main(String[] args) {
        //  You can add more test cases here
        int[] array1 = {1, 1, 1};
        int[] array2 = {1, 1, 1};
        int[] array3 = {1, 1};
        int[] array4 = {5,5};
//        System.out.println(solution(3, 1, 2, array1) == 3);
//        System.out.println(solution(3, 3, 5, array2) == 1);
//        System.out.println(solution(2, 1, 1, array3) == 2);
        System.out.println(solution(2, 0, 0, array4) == 0);
    }

    public static int solution(int n, int A, int B, int[] array_a) {

        // Please write your code here
        // 如果容量不够
        // 对10取余 就是个位数
        //
        int sum = 0;

        // 个位数
        for (int i = 0; i < n; i++) {
            sum += array_a[i];
        }
        int totalMod = sum % 10;
        sum = 0;
        if (A % 10 == totalMod || B % 10 == totalMod) {
            sum++;
        }

        int[][] dp = new int[array_a.length + 1][10];
        // 一般情况
        if ((A + B) % 10 == totalMod) {
            // 动态规划 计算

            dp[0][0] = 1;
            for (int i = 1; i < array_a.length + 1; i++) {
                    for (int j = 0; j < 10; j++) {
                        dp[i][j] += dp[i - 1][j];
                        // 原有的值也不能变
                        dp[i][(j + array_a[i - 1]) % 10] += dp[i - 1][j];

                    }

            }
            sum += dp[n][A];

            return sum;
        }


        return sum;
    }
}
